package bank;

import java.util.*;

public class _39CombinationSum {
    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        //  回溯法
        Set<List<Integer>> set = new HashSet<>();
        backtrack(candidates,target,new ArrayList<>(),set);
        return new ArrayList<>(set);
    }

    private static void backtrack(int[] candidates, int target, ArrayList<Integer> list, Set<List<Integer>> set) {
        if (listSum(list) > target){
            return ;
        }else if (listSum(list) == target){
            //  注意此处必须这么做，不然会导致list集合中下标的混乱
            List<Integer> list0 = new ArrayList<>(list);
            Collections.sort(list0);
            set.add(list0);
            return ;
        }
        for (int candidate : candidates) {
            list.add(candidate);
            backtrack(candidates, target, list, set);
            list.remove(list.size() - 1);
        }
    }

    private static int listSum(ArrayList<Integer> list) {
        int sum = 0;
        for (int i = 0;i < list.size();i++){
            sum += list.get(i);
        }
        return sum;
    }
}
